package string;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 30 Substring with Concatenation of All Words
 *
 You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in words exactly once and without any intervening characters.

 Example 1:

 Input:
 s = "barfoothefoobarman",
 words = ["foo","bar"]
 Output: [0,9]
 Explanation: Substrings starting at index 0 and 9 are "barfoo" and "foobar" respectively.
 The output order does not matter, returning [9,0] is fine too.
 Example 2:

 Input:
 s = "wordgoodgoodgoodbestword",
 words = ["word","good","best","word"]
 Output: []
 */
public class Q30_ConcatenationOfAllWords {

    /**
     * using hash, comparing the counts of words
     *
     * 1.brute force
     */
    private List<Integer> findSubstring(String s, String[] words) {
        List<Integer> ans = new ArrayList<>();
        int wordLen = words[0].length();
        int allLen = wordLen * words.length;
        Map<String, Integer> map = new HashMap<>();
        for (String word: words) {
            map.put(word, map.getOrDefault(word, 0)+1);
        }
        for (int i=0; i<s.length()-allLen+1; i++) {
            String w = s.substring(i, i+allLen);
            Map<String, Integer> tmpMap = new HashMap<>();
            //直接跨越 wordLen 的长度j=j+wordLen,不需要j++
            for (int j=0; j<w.length()-wordLen+1; j=j+wordLen) {
                String tmpW = w.substring(j, j+wordLen);
                tmpMap.put(tmpW, tmpMap.getOrDefault(tmpW, 0)+1);
            }
            if (map.equals(tmpMap)) {
                ans.add(i);
            }
        }
        return ans;
    }

    /**
     * 2.sliding window
     */
    private List<Integer> findSubstrWindow(String s, String[] words) {
        List<Integer> ans = new ArrayList<>();
        int wordLen = words[0].length();
        Map<String, Integer> map = new HashMap<>();
        for (String word: words) {
            map.put(word, map.getOrDefault(word, 0)+1);
        }
        //终止条件是 wordLen 完全可以覆盖，没有必要 s.length()-allLen+1
        for (int i=0; i<wordLen; i++) {
            int left = i;
            int right = i;
            int count = 0;
            Map<String, Integer> tmpMap = new HashMap<>();
            while (right < s.length()-wordLen+1) {
                String w = s.substring(right, right+wordLen);
                tmpMap.put(w, tmpMap.getOrDefault(w, 0)+1);
                count++;
                right = right + wordLen;
                while (tmpMap.get(w) > map.getOrDefault(w, 0)) {
                    String tmpW = s.substring(left, left+wordLen);
                    tmpMap.put(tmpW, tmpMap.get(w)-1);
                    count--;
                    left = left + wordLen;
                }
                if (count == words.length) {
                    ans.add(left);
                }
            }
        }
        return ans;
    }

    /**
     * sliding window optimization
     */
    private List<Integer> findSubstrWindowOpt(String s, String[] words) {
        List<Integer> ans = new ArrayList<>();
        int wordLen = words[0].length();
        Map<String, Integer> map = new HashMap<>();
        for (String word: words) {
            map.put(word, map.getOrDefault(word, 0)+1);
        }
        //终止条件是 wordLen 完全可以覆盖，没有必要 s.length()-allLen+1
        for (int i=0; i<wordLen; i++) {
            int left = i;
            int right = i;
            int count = 0;
            Map<String, Integer> tmpMap = new HashMap<>();
            while (right < s.length()-wordLen+1) {
                String w = s.substring(right, right+wordLen);
                right = right + wordLen;
                if (!map.containsKey(w)) {
                    count = 0;
                    left = right;
                    tmpMap.clear();
                } else {
                    count++;
                    tmpMap.put(w, tmpMap.getOrDefault(w, 0)+1);
                    while (tmpMap.get(w) > map.getOrDefault(w, 0)) {
                        String tmpW = s.substring(left, left+wordLen);
                        count--;
                        tmpMap.put(tmpW, tmpMap.get(w)-1);
                        left = left + wordLen;
                    }
                    if (count == words.length) {
                        ans.add(left);
                    }
                }
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        String s = "barfoothefoobarman";
        String[] words = new String[]{"foo","bar"};
        Q30_ConcatenationOfAllWords q30_concatenationOfAllWords = new Q30_ConcatenationOfAllWords();
        List<Integer> ans = q30_concatenationOfAllWords.findSubstring(s, words);
        ans.forEach(pos-> System.out.println(pos));
        List<Integer> ans2 = q30_concatenationOfAllWords.findSubstrWindow(s, words);
        ans2.forEach(pos-> System.out.println(pos));
        List<Integer> ans1 = q30_concatenationOfAllWords.findSubstrWindowOpt(s, words);
        ans1.forEach(pos-> System.out.println(pos));
    }



}
